package day01;

//    把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
//    给你一个可能存在重复元素值的数组numbers，它原来是一个升序排列的数组，
//    并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组[3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转
//    ，该数组的最小值为1。
public class Solution11 {
//    寻找数组中的最小值，旋转后存在数字k，数组下标0-k数组递增，k-n-1 数组递增，且numbers[0]>=numbers[n-1]



    // 测试用例1
    final static int[] test = new int[]{3,4,5,1,2};
    final static int[] test2 = new int[]{10,1,10,10,10};
    public static void main(String[] args){
        System.out.println(solution2(test2));
    }
    // 解法一：暴力破解
    public static int solution1(int[] numbers){
        int min = numbers[0];
        for( int i = 0; i < numbers.length; i++){
            if(min<numbers[i])
                min = numbers[i];
        }
        return min;
    }

    // 解法二：二分搜索
    /* 由两侧不断向中间搜索
       case 1: numbers[mid] > numbers[right] 此时最小值必定不在 mid 左侧，可能为 mid+1
       case 2: numbers[mid] < numbers[right] 此时最小值必定不在 mid 右侧，可能为 right
       case 3: numbers[mid] == numbers[right] 此时最小值必定在mid与right之间，(有误)
       case 3: numbers[mid] == numbers[right] 此时最小值在 left 与 right 之间 (存在重复元素)
               此时，若 left mid right 三处数值相同 或者left 比 mid right 大，left++，否则left最小


     */
    public static int solution2(int[] numbers){
        // 特例 numbers 为空，为1，为2,数组未经旋转
        if( numbers.length == 1){
            return numbers[0];
        }else if( numbers.length==2 ){
            if( numbers[0] > numbers[1]){
                return numbers[1];
            }else{
                return numbers[0];
            }
        }else if(numbers[0] < numbers[numbers.length-1]){
            return numbers[0];
        }else{
        // 一般情况
            int left = 0, right = numbers.length-1,mid;
            while(left <= right){
                mid = left + (right-left)/2;
                if(numbers[mid] > numbers[right]){
                    left = mid+1;
                }else if(numbers[mid] < numbers[right]){
                    right = mid;
                }else if(numbers[mid] == numbers[right]){

                    if(left==right){
                        break;
                    }else if(numbers[left]==numbers[mid]) {
                        left++;
                    }else if(numbers[left] < numbers[mid]) {
                        break;
                    }else if(numbers[left] > numbers[mid]){
                        left++;
                    }
                }
            }
            return numbers[left];
        }
    }


}


